import sys
data = sys.stdin.readlines()
#data = ["5 7", "1 3", "1 2", "2 4", "1 5" , "2 3", "3 4","4 3"]
#data = ["5 5", "1 2", "2 4", "2 3", "3 4","4 5"]

def read_data(edgelist):
    ncount, ecount = data[0].split()
    ncount, ecount = int(ncount), int(ecount)
    count = 0;
    for strin in data[1:]:
        ps1, ps2 = strin.split(" ");
        p1 = int(ps1)
        p2 = int(ps2)
        edgelist.append((p1,p2))
        count = count + 1
        if(count == ecount): break;
    return (ncount, ecount)

def create_adj_list(edgelist, ncount, ecount):
    adj_list = [];
    for i in range(0, ncount + 1):
        adj_list.append([])
    for edge in edgelist:
        adj_list[edge[0]].append(edge[1])
    return adj_list

WHITE = -1 # not visisted
GRAY = 0 # visiting
BLACK = 1 #visited

edgelist = []
ncount, ecount = read_data(edgelist)
#print(edgelist)
#print((ncount, ecount))

adj_list = create_adj_list(edgelist, ncount, ecount)
#print(adj_list)

routes = [0] * (ncount+1)
colors = [WHITE] * (ncount+1)
#print(routes)

poten_circle = []

def count_routes(node, poten_circle):
    if(node == ncount): return 1
    if (colors[node] == GRAY): 
        poten_circle.append(node)
        return 0
    if (colors[node] == BLACK): return routes[node]
    colors[node] = GRAY #color this node, for cycle detection.
    nextNodes = adj_list[node]
    for n in nextNodes:
        route_count = count_routes(n,poten_circle)
        routes[node] = routes[node] + route_count
    colors[node] = BLACK
    return routes[node]

total_route = count_routes(1, poten_circle) %  1000000000
if total_route == 0:
    print(0)
elif len(poten_circle) > 0:
    sum_circle = 0;
    for node in poten_circle:
        sum_circle = sum_circle + routes[node]
    if sum_circle > 0:
        print("INFINITE PATHS")
    else:
        print(total_route)
else:
    print(total_route)

